By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 20, Issue 3, pp. 405-602

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Fast Matching Algorithms for Points on a Polygon

Odile Marcotte and Subhash Suri

pp. 405-422

BibTeX  Abstract Full Text:  PDF

The Communication Complexity of Atomic Commitment and of Gossiping

Ouri Wolfson and Adrian Segall

pp. 423-450

BibTeX  Abstract Full Text:  PDF

Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses

Ulrich Baum and Michael Clausen

pp. 451-459

BibTeX  Abstract Full Text:  PDF

On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm

János Pach and Micha Sharir

pp. 460-470

BibTeX  Abstract Full Text:  PDF

Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

Mitsunori Ogiwara and Osamu Watanabe

pp. 471-483

BibTeX  Abstract Full Text:  PDF

Nondeterministic Computations in Sublogarithmic Space and Space Constructibility

Viliam Geffert

pp. 484-498

BibTeX  Abstract Full Text:  PDF

A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions

Uri Zwick

pp. 499-505

BibTeX  Abstract Full Text:  PDF

Near-Testable Sets

Judy Goldsmith, Lane A. Hemachandra, Deborah Joseph, and Paul Young

pp. 506-523

BibTeX  Abstract Full Text:  PDF

Compression and Ranking

Andrew V. Goldberg and Michael Sipser

pp. 524-536

BibTeX  Abstract Full Text:  PDF

Algorithms for Scheduling Imprecise Computations with Timing Constraints

Wei-Kuan Shih, Jane W. S. Liu, and Jen-Yao Chung

pp. 537-552

BibTeX  Abstract Full Text:  PDF

Boolean Functions, Invariance Groups, and Parallel Complexity

Peter Colte and Evangelos Kranakis

pp. 553-590

BibTeX  Abstract Full Text:  PDF

Tests for Permutation Polynomials

Joachim van zur Gathen

pp. 591-602

BibTeX  Abstract Full Text:  PDF